<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  
  <title>Dp题目 通配符匹配 | eric_cyr&#39;s blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="思路: 思路一: 利用两个指针进行遍历。 在代码里解释. 时间复杂度为:O(mn)O(mn)O(mn) 思路二: 动态规划 dp[i][j]表示s到i位置,p到j位置是否匹配! 初始化: dp[0][0]:什么都没有,所以为true 第一行dp[0][j],换句话说,s为空,与p匹配,所以只要p开始为*才为true 第一列dp[i][0],当然全部为False动态方程: 如果(s[i] &#x3D;&#x3D; p[">
<meta property="og:type" content="article">
<meta property="og:title" content="Dp题目 通配符匹配">
<meta property="og:url" content="http://yoursite.com/2020/06/14/Dp%E9%A2%98%E7%9B%AE-%E9%80%9A%E9%85%8D%E7%AC%A6%E5%8C%B9%E9%85%8D/index.html">
<meta property="og:site_name" content="eric_cyr&#39;s blog">
<meta property="og:description" content="思路: 思路一: 利用两个指针进行遍历。 在代码里解释. 时间复杂度为:O(mn)O(mn)O(mn) 思路二: 动态规划 dp[i][j]表示s到i位置,p到j位置是否匹配! 初始化: dp[0][0]:什么都没有,所以为true 第一行dp[0][j],换句话说,s为空,与p匹配,所以只要p开始为*才为true 第一列dp[i][0],当然全部为False动态方程: 如果(s[i] &#x3D;&#x3D; p[">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2020-06-14T13:57:50.000Z">
<meta property="article:modified_time" content="2020-06-14T13:57:59.525Z">
<meta property="article:author" content="eric_cyr">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="eric_cyr&#39;s blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.1"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">eric_cyr&#39;s blog</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">分享是程序员的第一美德</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-Dp题目-通配符匹配" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/06/14/Dp%E9%A2%98%E7%9B%AE-%E9%80%9A%E9%85%8D%E7%AC%A6%E5%8C%B9%E9%85%8D/" class="article-date">
  <time datetime="2020-06-14T13:57:50.000Z" itemprop="datePublished">2020-06-14</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      Dp题目 通配符匹配
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>思路:</p>
<p>思路一: 利用两个指针进行遍历。</p>
<p>在代码里解释.</p>
<p>时间复杂度为:O(mn)O(mn)O(mn)</p>
<p>思路二: 动态规划</p>
<p>dp[i][j]表示s到i位置,p到j位置是否匹配!</p>
<p>初始化:</p>
<pre><code>dp[0][0]:什么都没有,所以为true
第一行dp[0][j],换句话说,s为空,与p匹配,所以只要p开始为*才为true
第一列dp[i][0],当然全部为False</code></pre><p>动态方程:</p>
<pre><code>如果(s[i] == p[j] || p[j] == &quot;?&quot;) &amp;&amp; dp[i-1][j-1] ,有dp[i][j] = true

如果p[j] == &quot;*&quot; &amp;&amp; (dp[i-1][j] = true || dp[i][j-1] = true) 有dp[i][j] = true

​ note:

​ dp[i][j-1],表示*代表是空字符,例如ab,ab*

​ dp[i-1][j],表示*代表非空任何字符,例如abcd,ab*</code></pre><p>​</p>
<p>class Solution {<br>    public boolean isMatch(String s, String p) {<br>        int sn = s.length();<br>        int pn = p.length();<br>        int i = 0;<br>        int j = 0;<br>        int start = -1;<br>        int match = 0;<br>        while (i &lt; sn) {<br>            if (j &lt; pn &amp;&amp; (s.charAt(i) == p.charAt(j) || p.charAt(j) == ‘?’)) {<br>                i++;<br>                j++;<br>            } else if (j &lt; pn &amp;&amp; p.charAt(j) == ‘<em>‘) {<br>                start = j;<br>                match = i;<br>                j++;<br>            } else if (start != -1) {<br>                j = start + 1;<br>                match++;<br>                i = match;<br>            } else {<br>                return false;<br>            }<br>        }<br>        while (j &lt; pn) {<br>//plan b<br>class Solution {<br>    public boolean isMatch(String s, String p) {<br>        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];<br>        dp[0][0] = true;<br>        for (int j = 1; j &lt; p.length() + 1; j++) {<br>            if (p.charAt(j - 1) == ‘</em>‘) {<br>                dp[0][j] = dp[0][j - 1];<br>            }<br>        }<br>        for (int i = 1; i &lt; s.length() + 1; i++) {<br>            for (int j = 1; j &lt; p.length() + 1; j++) {<br>                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == ‘?’) {<br>                    dp[i][j] = dp[i - 1][j - 1];<br>                } else if (p.charAt(j - 1) == ‘*’) {<br>                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];<br>                }<br>            }<br>        }<br>        return dp[s.length()][p.length()];</p>
<pre><code>}</code></pre><p>}</p>
<p>if (p.charAt(j) != ‘*’) return false;<br>            j++;<br>        }<br>        return true;</p>
<pre><code>}</code></pre><p>}</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/06/14/Dp%E9%A2%98%E7%9B%AE-%E9%80%9A%E9%85%8D%E7%AC%A6%E5%8C%B9%E9%85%8D/" data-id="ckbq7rmlj0002ig1lbin2al3j" class="article-share-link">Share</a>
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2020/06/14/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          背包问题总结
        
      </div>
    </a>
  
  
    <a href="/2020/06/14/%E9%BB%91%E5%AE%A2%E4%B8%8E%E7%94%BB%E5%AE%B6/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">黑客与画家</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/06/">June 2020</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/05/">May 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/06/22/vue-%E7%BB%84%E4%BB%B6%E9%80%9A%E4%BF%A1/">vue 组件通信</a>
          </li>
        
          <li>
            <a href="/2020/06/14/njuoj-%E9%80%92%E5%BD%92%E6%9F%A5%E8%AF%A2%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2/">njuoj 递归查询子字符串</a>
          </li>
        
          <li>
            <a href="/2020/06/14/foo-bar-%E7%9A%84%E6%95%85%E4%BA%8B/">foo bar 的故事</a>
          </li>
        
          <li>
            <a href="/2020/06/14/pwa/">pwa</a>
          </li>
        
          <li>
            <a href="/2020/06/14/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93/">背包问题总结</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 eric_cyr<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>




<script src="/js/script.js"></script>




  </div>
</body>
</html>